%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Cryptography
%% http://code.google.com/p/crypto-book/
%%
%% Copyright (C) 2007--2010 David R. Kohel <David.Kohel@univmed.fr>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Elementary Number Theory}
\label{chap:number_theory}
\index{number theory}

Recall that $\F_2[x]$\index{finite field!$\F_2$} is the
ring\index{ring} of all polynomials\index{polynomial!ring} with
coefficients in $\F_2 = \{0, 1\}$. In this chapter we assume that $R$
is one of the rings $\Z$ or $\F_2[x]$, $m$ is an element of $R$, and
we denote by $(m)$ or $mR$ the set $\{mx \mid x \in R\}$, which is
called an \emph{ideal}\index{ideal} of $R$. The principal goal is to
present the \emph{quotient}\index{quotient} or
\emph{residue class ring}\index{ring!residue class} $R/mR$ and to
understand how to work with its elements. We refer to $m$ as the
\emph{modulus}\index{modulus} of $R/mR$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Quotient rings}
\index{ring!quotient}

The residue\index{ring!residue class} class ring $R/mR$ is a
commutative\index{ring!commutative} ring. Elements of $R/mR$ are sets,
called \emph{cosets}\index{coset} of $mR$, of the form
\[
\quo{a}
=
a + mR
=
\{a + mx \mid x \in R\}
\]
and multiplication and addition laws are derived from those on $R$:
%%
\begin{align*}
\quo{a} + \quo{b}
&=
(a + mR) + (b + mR)
=
(a+b) + mR
=
\quo{(a + b)}, \\[4pt]
\quo{a} * \quo{b}
&= (a + mR) * (b + mR)
=
(a*b) + mR
=
\quo{(a * b)}.
\end{align*}
%%
The fact that $R/mR$\index{ring!residue class} is a ring\index{ring}
means that addition ($+$) and multiplication $(*)$ are well-defined on
cosets\index{coset}, and satisfy the usual
associative\index{associative} and distributive\index{distributive}
laws.

\begin{example}
\rm
Consider the ring $R/mR = \Z/m\Z$ with modulus $m = 21$. We consider
the addition and multiplication of $\quo{2} = \quo{23}$ and
$\quo{-2} = \quo{19}$, and show that in each pair of equal elements
we can use either the first or the second representative to define the
sum and product.  First, for addition we find
\[
\quo{2} + \quo{-2}
=
\quo{2 + (-2)}
=
\quo{0}
\]
but on the other hand
\[
\quo{23} + \quo{19}
=
\quo{23 + 19}
=
\quo{42}
\]
which equals $\quo{0}$ since $42$ is in $21\Z$.  Multiplication is
similarly independent of the representatives we choose:
\[
\quo{2} * \quo{-2}
=
\quo{2 * (-2)}
=
\quo{-4} = \quo{17}
\]
which holds since $-4 = 17 + (-1)*21$, or
\[
\quo{23} + \quo{19}
=
\quo{437}
=
\quo{17}
\]
where the latter identity is determined by
$437 = 17 + 420 = 17 + 20*21$. \qed
\end{example}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{The $\bmod$ operator}
\index{$\bmod$}
\index{modulus}

In both the rings $R = \Z$ and $R = \F_2[x]$, we have an operator
$\bmod~m$ for producing a canonical smallest representative for
elements of the quotient\index{ring!quotient} rings $R/mR$.  This
means that we can work with this smallest or reduced representative in
computations in $R/mR$. In particular, we note that working with this
representative is well-defined:
%%
\begin{align*}
\big((a \bmod m) + (b \bmod m)\big) \bmod m
&=
(a + b) \bmod m \\[4pt]
\big((a \bmod m) * (b \bmod m)\big) \bmod m
&=
(a * b) \bmod m
\end{align*}
%%
since $a \bmod m = b \bmod m$ if and only if $\quo{a} = \quo{b}$.

The value $a \bmod m$ can be computed by long
division\index{long division}, i.e. successively subtracting off
multiples until the final result is smaller than $m$. The definition
of ``$x$ smaller than $y$'' is $x < y$ for positive $x,y \in \Z$, and
$\deg(x) < \deg(y)$\index{$\deg$}\index{polynomial!degree} for
polynomials\index{polynomial}
$x,y \in \F_2[x]$\index{ring!polynomial}\index{finite field!$\F_2$}.

\begin{definition}
Using the $\bmod$ operator, we define a
\emph{boolean operator}\index{operator!boolean}
$\_ \equiv \_ \bmod m$\index{$\equiv$} such that the value
$a \equiv b \bmod m$ is {\tt True} if and only if $(a - b) \bmod m$ is
zero. The operator ``$\equiv$'' is read
``equivalent''\index{equivalent}. If $a \equiv b \mod m$, then we say
that $a$ is equivalent to $b$ modulo $m$.
\end{definition}

In the ring $\Z$, the expression $a \bmod b$ is usually understood to
mean the remainder obtained when $a$ is divided by $b$. Thus given
two integers $a$ and $b$ and a positve integer $m$, we have
$a \equiv b \bmod m$ if and only if both $a$ and $b$ leave the same
nonnegative remainder upon division by $m$. For instance,
$3 \bmod 2 = 1$ because we obtain a remainder of $1$ after dividing
$3$ by $2$.
%% Furthermore, any two even integers are congruent modulo
%% $2$, and any two odd integers are congruent modulo $2$.

\begin{example}
Use the operator $\bmod$ to determine a canonical representative for
$x^7$ in $\F_2[x] / (x^2 + x + 1)$.
\end{example}

\begin{proof}[Solution]
First we write $x^7 = (x^3)^2*x$ and compute:
%%
\begin{align*}
x^3 \bmod (x^2 + x + 1)
&= \big(x^3 + x* (x^2 + x + 1)\big) \bmod (x^2 + x + 1) \\[4pt]
&= (x^2 + x) \bmod (x^2 + x + 1) \\[4pt]
&= \big((x^2 + x) + (x^2 + x + 1)\big) \bmod (x^2 + x + 1) \\[4pt]
&= 1.
\end{align*}
%%
It follows that
%%
\begin{align*}
x^7 \bmod x^2 + x + 1
&=
(1^2 * x) \bmod (x^2 + x + 1) \\[4pt]
&=
x.
\end{align*}
%%
By explicit long division\index{long division}:
\[
\begin{array}[t]{r@{}*{12}{l@{\,}}}
       && x^5 + & x^4 + &     & & x^2 &+& x  \\ \cline{2-9}
x^2+x+1 &
  \big) & x^7 \\
       && x^7 + & x^6 + & x^5 \\ \cline{3-5}
       &&       & x^6 + & x^5 \\
       &&       & x^6 + & x^5 &+& x^4 \\ \cline{4-7}
       &&       &       &     & & x^4   &     \\
       &&       &       &     & & x^4 &+& x^3 &+& x^2 \\ \cline{7-11}
       &&       &       &     & &     & & x^3 &+& x^2   &   \\
       &&       &       &     & &     & & x^3 &+& x^2 &+& x \\ \cline{9-13}
       &&       &       &     & &     & &     & &     & & x \\
\end{array}
\]
we find similarly that $x^7 = (x^5+x^4+x^2+x)*(x^2+x+1) + x$, verifying
the equality $x^7 \bmod (x^2+x+1) = x$.
\end{proof}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Primes and irreducibles}

A nonzero ideal $(p)$ in $R$~($= \Z$ or $\F_2[x]$) is said to be a
\emph{prime ideal}\index{ideal!prime} if $p$ is a prime number or an
irreducible polynomial. In the context of $\Z$,
Fermat's\index{Fermat!little theorem} little theorem states that if
$p > 1$ is prime and $a$ is any integer such that
$a \not\equiv 0 \bmod p$, then $a^{p-1} \equiv 1 \bmod p$. The
following theorem is a generalization of
Fermat's\index{Fermat!little theorem} little theorem.

\begin{theorem}
Let $(p)$ be a prime ideal of $R$ and let $N = \#R/(p) - 1$.
Then $\quo{a}^N = 1$ for every nonzero $\quo{a} \in R/(p)$. Conversely
if there exists an element $\quo{a} \in R/(p)$ of exact order $N$,
then $(p)$ is prime.
\end{theorem}

Recall that we define the polynomial $g(x)$ to be primitive if
and only if the element $\quo{x}$ has exact order $N$ in $R/(g(x))$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Constructing irreducible polynomials}

We now want to enumerate the the irreducible polynomials in $\F_2[x]$
of low degree, and in the process explain some of the steps for more
efficiently determining (ir)reducibility of polynomials.

\paragraph{Degree 1}
The linear polynomials $x$ and $x+1$ are necessarily irreducible.

\paragraph{Degree 2}
The polynomial $x^2 + x + 1$ is irreducible by the previous theorem
and the fact that $\quo{x}$, $\quo{x}^2 = \quo{x} + 1$, and
$\quo{x}^3 = 1$. Conversely, it is clear that the only other
candidates---$x^2$, $x^2 + x$, and $x^2 + 1 = (x + 1)^2$---are
reducible.

\begin{lemma}
If $f(x)$ is a polynomial, then $f(x) \bmod (x - a) = f(a)$ and
in particular $f(x) = (x - a)g(x)$ if and only if $f(a) = 0$.
\end{lemma}

For polynomials over $\F_2$, the value $f(0)$ is the constant term
and $f(1)$ is the number of nonzero coefficients $\bmod 2$, which
gives an easy test for divisibility by linear polynomials.

\paragraph{Degree 3}
By the previous test, it is clear that the only nontrivial candidates
to consider are
\[
x^3 + x + 1,\qquad x^3+x^2+1
\]
and these are automatically irreducible, since they have no linear
factor.

\paragraph{Degree 4}
We first exclude $(x^2 + x + 1)^2 = x^4 + x^2 + 1$, the only degree
four polynomial that is divisible by an irreducible polynomial of
degree $2$. Every other reducible polynomial must therefore have a
divisor of degree $1$ and we apply the lemma to reduce to the list of
irreducible polynomials:
\[
x^4 + x^3 + 1,\qquad x^4 + x + 1,\qquad x^4 + x^3 + x^2 + x + 1.
\]

\paragraph{Degree 5}
As in degree $4$, we exclude those polynomials that have a divisor of
degree $2$:
%%
\begin{align*}
(x^2 + x + 1) (x^3 + x + 1) &= x^5 + x^4 + 1 \\[4pt]
(x^2 + x + 1) (x^3 + x^3 + 1) &= x^5 + x + 1
\end{align*}
%%
Conclude that all other polynomials of degree $5$ with constant term
$1$ and an odd number of coefficients are irreducible:
%%
\begin{align*}
x^5 + x^3 + 1, &\quad x^5 + x^2 + 1, \\[4pt]
x^5 + x^4 + x^3 + x^2 + 1, &\quad x^5 + x^4 + x^3 + x + 1, \\[4pt]
x^5 + x^4 + x^2 + x + 1, &\quad x^5 + x^3 + x^2 + x + 1.
\end{align*}

\noindent{\bf Exercise.}
Determine which of the above polynomials are primitive.



\subsection*{Cyclotomic polynomials}

In the previous lecture we found that there are six irreducible
polynomials of degree five.  In order to understand and to count
the numbers of irreducible and primitive polynomials, we first
introduce cyclotomic polynomials.

\begin{definition}
The cyclotomic polynomials $\Phi_N(x)$ are defined recursively
by the identity:
$$
x^N-1 = \prod_{m|N} \Phi_m(x).
$$
\end{definition}

\begin{example}
To demonstrate how this serves to define the cyclotomic polynomials,
we compute the first few examples:
$$
\begin{array}{ll}
\Phi_1(x) = x-1     & \Phi_4(x) = x^2+1 \\
\Phi_2(x) = x+1     & \Phi_5(x) = x^4+x^3+x^3+x^2+x+1 \\
\Phi_3(x) = x^2+x+1 & \Phi_6(x) = x^2-x+1
\end{array}
$$
Moreover, if $p$ is a prime, then
$$
\Phi_p(x) = \frac{x^p-1}{x-1} = x^{p-1}+\cdots+x+1.
$$
\end{example}

So far, the definition of cyclotomic polynomials does not make use
of polynomials being defined over $\F_2$, and if we instead let
the coefficient ring be $\Z$, then we have the following classical
result.

\begin{theorem}
The cyclotomic polynomial $\Phi_N(x)$ is irreducible over $\Z$, of
degree $\varphi(N)$.
\end{theorem}

The function $\varphi(N)$ is called the Euler $\varphi$-function,
and is defined by
$$
\varphi(N) = \prod_{p^r||N} p^{r-1}(p-1),
$$
where $p^r||N$ means that $p^r$ divides $N$ but that $p^{r+1}$ does
not divide $N$.

The analogous statement about irreducibility over $\F_2$ is false,
but we can make a very precise statement of the form of the
factorization of cyclotomic polynomials over $\F^2$.

\begin{theorem}
An irreducible polynomial $g(x) \in \F_2[x]$ of degree $n$ divides
the polynomial $x^N+1$ and no other polynomial $x^m+1$ for $m < N$
if and only if $g(x)$ divides $\Phi_N(x)$.
The integer $N$ equals $2^n-1$ if and only if $g(x)$ is primitive.
\end{theorem}

\begin{corollary}
The cyclotomic polynomial $\Phi_N(x) \in \F_2[x]$ for $N = 2^n-1$
is the product of the distinct primitive polynomials of degree $n$.
\end{corollary}

\begin{example}
Previously we found that there were $6$ irreducible
polynomials of degree $5$ in $\F_2[x]$.  Since $N = 2^5-1 = 31$ is
prime, every irreducible polynomial of degree $5$ is in fact primitive.
Since the degree of $\Phi_{31}(x)$ is $\varphi(31) = 31-1 = 30$,
we could have concluded in advance that there were exactly $6$
primitive and irreducible polynomials of this degree.
\end{example}

\subsection*{LFSR cryptosystems}

Since the period $N = 2^n-1$ of the LFSR output sequence, with
primitive connection polynomial, grows exponentially in the size
of $n$, LFSR's provide good constructions for sequences of large
period.  Moreover a LFSR can be made computationally efficient
by choosing a sparse primitive polynomial such as
$$
\begin{array}{rl}
14: & x^{14} + x^7 + x^5 + x^3 + 1 \\
15: & x^{15} + x^5 + x^4 + x^2 + 1 \\
16: & x^{16} + x^5 + x^3 + x^2 + 1 \\
17: & x^{17} + x^3 + 1
\end{array}
$$
A na\"{\i}ve stream cryptosystem can be built from a LFSR by
taking the bit sum of the keystream with the message stream to
produce ciphertext.  Unfortunately, knowledge of just $2n$ bits
of the LFSR keysteam allows the determination of the entire
sequence, by an algorithm due to Berlekamp and Massey.  Therefore
such a LFSR cryptosystem should be considered insecure.
A relatively new stream cryptosystem, called the {\em shrinking
generator} cryptosystem, using two LFSR's in unison, has so far
resisted any such algorithms.

\subsection*{Shrinking Generator cryptosystem}

Let $L_1$ and $L_2$ be two LFSR's with output sequences $a_0a_1a_2\dots$
and $s_0s_1s_2\dots$.  The first sequence is called the input sequence
and the second sequence the controlling sequence.  At clock cycle
$i$ bits $a_i$ and $s_i$ are output.  If $s_i$ is $0$ then the bit
$a_i$ is discarded, and otherwise $a_i$ is output as part of the output
keystream.  The resulting keystream
$$
z_1z_2z_3\dots z_n\dots = a_{i_1}a_{i_2}a_{i_3}\dots a_{i_n}\dots
$$
is used for forming the bit sum with the message stream to form ciphertext.

\section*{Exercises}

\input{exercises/number-theory}
